package interview;

import java.util.*;

public class lc54 {
    public static void main(String[] args) {
        System.out.println(spiralOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}}));
        System.out.println(spiralOrder(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}));
    }
    public static List<Integer> spiralOrder(int[][] matrix) {
        int up = 0, down = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        List<Integer> ans = new ArrayList<>();
        while (left <= right && up <= down){
            int i = left;
            while(i <= right){
                ans.add(matrix[up][i]);
                i++;
            }
            up++;
            i = up;
            if(up > down)
                break;
            while (i <= down){
                ans.add(matrix[i][right]);
                i++;
            }
            right--;
            i = right;
            if(right < left)
                break;
            while (i >= left){
                ans.add(matrix[down][i]);
                i--;
            }
            down--;
            i = down;
            if(down < up)
                break;
            while (i >= up){
                ans.add(matrix[i][left]);
                i--;
            }
            left++;
            if(left > right)
                break;
        }
        return ans;
    }
}
